package com.promote.algorithm;

/**
 * @ClassName Rotate
 * Description 旋转数组
 * @Author LiZiHao
 * Date 2022/3/7 15:28
 * @Version 1.0
 **/
public class Rotate {

    /**
     *  给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
     *  方法一：使用临时数组
     * @param nums 给定的数组
     * @param k 旋转的位置数
     */
    public void rotateOne(int[] nums, int k) {

        int length = nums.length;
        int[] temp = new int[length];

        //将原始数组放到一个临时数组
        for (int i = 0; i < length; i++ ) {
            temp[i] = nums[i];
        }

        //将临时数组放到原始数组，并根据k值旋转数组
        for (int i = 0; i < length; i++) {
            nums[(i+k)%length] = temp[i];
        }
    }

    /**
     * 方法二 先反转前面的，后反转后面的k个，最后反转全部
     * @param nums
     * @param k
     */
    public void rotateTwo(int[] nums, int k) {
        int length = nums.length;
        k %= length;
        //先反转前面的
        reverse(nums,0,length-k-1);
        //后反转后面的k个
        reverse(nums,length-k,length-1);
        //最后反转全部
        reverse(nums,0,length-1);
    }

    //把数组从start 、end 之间的元素交换
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end --] = temp;
        }
    }

    /**
     * 给定一个 n×n 的二维矩阵matrix 表示一个图像。请你将图像顺时针旋转 90 度。
     *
     * 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
     * 先上下交换，在左右交换
     *
     */
    public void rotateThree(int[][] matrix) {
        int length = matrix.length;

        //先上下交换
        for (int i = 0; i < length / 2; i++) {
            int[] temp = matrix[i];
            matrix[i] = matrix[length - i - 1];
            matrix[length - i - 1] = temp;
        }

        //在按对角线交换
        for (int i = 0; i < length; ++i) {
            for (int j = i+1; j < length; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}
